#include <string>
#include <iostream>
#include "list.h"

using namespace std;

list::list() : head(nullptr), tail(nullptr)
{
}

list::~list()
{
    clear();
}

void list::push_back(int data)
{
    /**
     * 1. 判断头指针是否为空
     *      头指针为空说明为空链表，将节点赋值给头指针
     *      头指针不为空说明该链表存在数据节点，将节点添加到链表尾部
    */
    Node *node = new Node;
    node->data = data;
    if(head == nullptr) {
        node->next = nullptr;
        node->pre = nullptr;

        head = node;
        tail = node;
    }
    else {
        tail->next = node;
        node->next = nullptr;
        node->pre = tail;

        tail = node;
    }
    ++length;
}

void list::push_front(int data)
{
    /**
     * 1. 判断头指针是否为空
     *      头指针为空说明为空链表，将节点赋值给头指针
     *      头指针不为空说明该链表存在数据节点，将节点添加到链表头部
    */
    Node *node = new Node;
    node->data = data;
    if(head == nullptr) {
        node->next = nullptr;
        node->pre = nullptr;

        head = node;
        tail = node;
    }
    else {
        node->pre = nullptr;
        node->next = head;

        head = node;
    }
    ++length;
}

void list::insert(int index, int data)
{
    /**
     * 1. 判断下标是否超范围，超范围抛出异常
     * 2. 当 index 为 0 时使用头插，index 为链表长度时使用尾插
     * 3. 当在中间插入时，需要先遍历链表，找到相应下标的指针
    */
    if(index < 0 || index > length) {
        throw string("index out of range.");
    }
    if(index == 0)
        push_front(data);
    if(index == length)
        push_back(data);
    
    Node* p = head;
    int pos = 0;
    while (p != nullptr)
    {
        p = p->next;
        ++pos;
        if(pos == index)
            break;
    }
    
    Node *node = new Node;
    node->data = data;
    p->pre = node;
    p->pre->next = node;
    node->pre = p->pre;
    node->next = p;
    ++length;
}

void list::pop_back()
{
    Node *p = tail;
    /**
     * 1. p == nullptr 已经为空链表
     * 2. p->pre ！= nullptr 链表数据超过 2
     * 3. p->pre == nullptr 链表只有当前一个节点
    */
    if(p == nullptr) {
        return;
    }
    if(p->pre != nullptr) {
        tail = p->pre;
        p->pre->next = nullptr;
    }
    else {
        head = nullptr;
        tail = nullptr;
    }

    delete p;
    p = nullptr;
    --length;
}

void list::pop_front()
{
    Node *p = head;
    if(p == nullptr)
        return;
    if(p->next != nullptr) {
        head = p->next;
        p->next->pre = nullptr;
    }
    else {
        head = nullptr;
        tail = nullptr;
    }

    delete p;
    p = nullptr;
    --length;
}

void list::remove(int index)
{
    if(index < 0 || index >= length) {
        throw string("index out of range.");
    }
    Node* p = head;
    if(p == nullptr)
        return;
    if(index == 0)
        pop_front();
    if(index == length - 1)
        pop_back();
    
    int pos = 0;
    while (p != nullptr)
    {
        p = p->next;
        ++pos;
        if(pos == index)
            break;
    }

    p->pre->next = p->next;
    p->next->pre = p->pre;

    delete p;
    p = nullptr;

    --length;
}

void list::clear()
{
    while (head != nullptr)
    {
        pop_back();
    }    
}

bool list::empty()
{
    return length > 0 ? false : true;
}

int list::size() const
{
    return length;
}

void list::visit()
{
    Node* p = head;
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;    
}